查看原文
其他

系统是如何给你匹配瓜皮队友的?

Github喵 2022-06-18

The following article is from labuladong Author labuladong

写这篇的文章的原因是玩 LOL 手游。

我有个朋友抱怨说打排位匹配的队友太菜了,我就说我打排位觉得队友都挺行的啊?我经常躺赢。

朋友意味深长地说了句:一般隐藏分比较高的玩家,排位如果排不到实力相当的队友,就会排到一些菜狗。

嗯?我想了几秒钟感觉这小伙子不对劲,他意思是说我隐藏分低,还是说我就是那条菜狗?

我立马要求和他开黑打一把,证明我不是菜狗,他才是菜狗。

完之后我就来发文了,虽然结果不便透露,但我对游戏的匹配机制有了一点思考。

所谓「隐藏分」我不知道是不是真的,毕竟匹配机制是所有竞技类游戏的核心环节,想必非常复杂,不是简单几个指标就能搞定的

但是如果把这个「隐藏分」机制简化,倒是一个值得思考的算法问题:系统如何以不同的随机概率进行匹配?

或者简单点说,如何带权重地做随机选择?

不要觉得这个很容易,如果给你一个长度为n的数组,让你从中等概率随机抽取一个元素,你肯定会做,random 一个[0, n-1]的数字出来作为索引就行了,每个元素被随机选到的概率都是1/n

但假设每个元素都有不同的权重,权重地大小代表随机选到这个元素的概率大小,你如何写算法去随机获取元素呢?

力扣第 528 题「按权重随机选择」就是这样一个问题:

我们就来思考一下这个问题,解决按照权重随机选择元素的问题。

解法思路

首先回顾一下我们和随机算法有关的历史文章:

前文 设计随机删除元素的数据结构 主要考察的是数据结构的使用,每次把元素移到数组尾部再删除,可以避免数据搬移。

前文 无限序列中随机抽取元素 讲的是经典的「水塘抽样算法」,运用简单的数学运算,在无限序列中等概率选取元素。

前文 算法笔试技巧 中我还分享过一个巧用概率最大化测试用例通过率的骗分技巧。

不过上述旧文并不能解决本文提出的问题,反而是前文 前缀和技巧 加上 二分搜索详解 能够解决带权重的随机选择算法

这个随机算法和前缀和技巧和二分搜索技巧能扯上啥关系?且听我慢慢道来。

假设给你输入的权重数组是w = [1,3,2,1],我们想让概率符合权重,那么可以抽象一下,根据权重画出这么一条彩色的线段:

如果我在线段上面随机丢一个石子,石子落在哪个颜色上,我就选择该颜色对应的权重索引,那么每个索引被选中的概率是不是就是和权重相关联了?

所以,你再仔细看看这条彩色的线段像什么?这不就是 前缀和数组

那么接下来,如何模拟在线段上扔石子?

当然是随机数,比如上述前缀和数组preSum,取值范围是[1, 7],那么我生成一个在这个区间的随机数target = 5,就好像在这条线段中随机扔了一颗石子:

还有个问题,preSum中并没有 5 这个元素,我们应该选择比 5 大的最小元素,也就是 6,即preSum数组的索引 3:

如何快速寻找数组中大于等于目标值的最小元素?这里就要用到 二分搜索 了,确切地说是搜索左侧边界的二分搜索

到这里,这道题的核心思路就说完了,主要分几步:

1、根据权重数组w生成前缀和数组preSum

2、生成一个取值在preSum之内的随机数,用二分搜索算法寻找大于等于这个随机数的最小元素索引。

3、最后对这个索引减一(因为前缀和数组有一位索引偏移),就可以作为权重数组的索引,即最终答案:

解法代码

上述思路应该不难理解,但是写代码的时候坑可就多了。

要知道涉及开闭区间、索引偏移和二分搜索的题目,需要你对算法的细节把控非常精确,否则会出各种难以排查的 bug。

下面来抠细节,继续前面的例子:

就比如这个preSum数组,你觉得随机数target应该在什么范围取值?闭区间[0, 7]还是左闭右开[0, 7)

都不是,应该在闭区间[1, 7]中选择,因为前缀和数组中 0 本质上是个占位符,仔细体会一下:

所以要这样写代码:

int n = preSum.length;
// target 取值范围是闭区间 [1, preSum[n - 1]]
int target = rand.nextInt(preSum[n - 1]) + 1;

接下来,在preSum中寻找大于等于target的最小元素索引,应该用什么品种的二分搜索?搜索左侧边界的还是搜索右侧边界的?

实际上应该使用搜索左侧边界的二分搜索:

// 搜索左侧边界的二分搜索
int left_bound(int[] nums, int target) {
    if (nums.length == 0return -1;
    int left = 0, right = nums.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left;
}

前文 二分搜索详解 着重讲了数组中存在目标元素重复的情况,没仔细讲目标元素不存在的情况。

当目标元素target不存在数组nums中时,搜索左侧边界的二分搜索的返回值可以做以下几种解读

1、返回的这个值是nums中大于等于target的最小元素索引。

2、返回的这个值是target应该插入在nums中的索引位置。

3、返回的这个值是nums中小于target的元素个数。

比如在有序数组nums = [2,3,5,7]中搜索target = 4,搜索左边界的二分算法会返回 2,你带入上面的说法,都是对的。

所以以上三种解读都是等价的,可以根据具体题目场景灵活运用,显然这里我们需要的是第一种。

综上,我们可以写出最终解法代码:

class Solution {
    // 前缀和数组
    private int[] preSum;
    private Random rand = new Random();

    public Solution(int[] w) {
        int n = w.length;
        // 构建前缀和数组,偏移一位留给 preSum[0]
        preSum = new int[n + 1];
        preSum[0] = 0;
        // preSum[i] = sum(w[0..i-1])
        for (int i = 1; i <= n; i++) {
            preSum[i] = preSum[i - 1] + w[i - 1];
        }
    }

    public int pickIndex() {
        int n = preSum.length;
        // 在闭区间 [1, preSum[n - 1]] 中随机选择一个数字
        int target = rand.nextInt(preSum[n - 1]) + 1;
        // 获取 target 在前缀和数组 preSum 中的索引
        // 搜索左侧边界的二分搜索
        int left = 0, right = n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (preSum[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        // preSum 的索引偏移了一位,还原为权重数组 w 的索引
        return left - 1;
    }
}

有了之前的铺垫,相信你能够完全理解上述代码,这道随机权重的题目就解决了。

经常有读者留言调侃,每次都是看我的文章「云刷题」,看完就会了,也不用亲自动手刷了。

但我想说的是,很多题目思路一说就懂,但是深入一些的话很多细节都可能有坑,本文讲的这道题就是一个例子,所以还是建议多实践,多总结。


·················END·················
往期推荐:
Ubuntu 22.04 震撼登场!!!
这 4 个远程桌面开源了!
可怕!CPU暗藏了这些未公开的指令!
另外欢迎大家围观我的朋友圈,搞搞技术,吹吹牛逼。另外朋友圈会发一些外包单,方便自己没时间的时候,小伙伴可以一起利用技术接一些副业项目赚钱

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存